package algorithm.recursionAndbacktrack.combination.p40;

import java.util.*;

class Solution {
    private List<List<Integer>> combinations;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        combinations = new ArrayList<>();
        if (candidates != null && candidates.length > 0) {
            Arrays.sort(candidates);
            combinationSum2(candidates, new boolean[candidates.length], 0, target, new ArrayDeque<>());
        }
        return combinations;
    }

    public void combinationSum2(int[] candidates, boolean[] used, int startIndex, int target, Deque<Integer> combination) {
        if (target <= 0) {
            if(target == 0)
                combinations.add(new ArrayList<>(combination));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (used[i] || (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1])) {
                continue;
            }
            used[i] = true;
            combination.addLast(candidates[i]);
            combinationSum2(candidates, used, i + 1, target - candidates[i], combination);
            combination.removeLast();
            used[i] = false;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().combinationSum2(new int[]{10,1,2,7,6,1,5}, 8));
    }
}